package com.dzu.medium;

/**
 * @author ZhaoDong
 * @date 2022/10/12 10:15
 * @description 198. 打家劫舍
 */
public class Test198 {
    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 7, 9, 3, 1, 3}));
    }

    public static int rob2(int[] nums) {
        int prev = 0;
        int curr = 0;

        // 每次循环，计算“偷到当前房子为止的最大金额”
        for (int i : nums) {
            // 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
            // dp[k] = max{ dp[k-1], dp[k-2] + i }
            int temp = Math.max(curr, prev + i);
            prev = curr;
            curr = temp;
            // 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
        }

        return curr;

    }


    public static int rob(int[] nums) {

        if (nums.length == 1) {
            return nums[0];
        }
        int[] f = new int[nums.length];
        f[0] = nums[0];
        f[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            f[i] = Math.max(f[i - 1], f[i - 2] + nums[i]);

        }
        return f[f.length - 1];

    }
}
